2617. 网格图中最少访问的格子数

题目

思路

参考题解：2617. 网格图中最少访问的格子数题解 - 力扣（LeetCode）

一：BFS + 并查集

枚举下一步的所有选择，记录步数。
枚举过程中，需要标记之前走过的点并跳过（再次走到之前走过的点的步数必然大于第一次走到这个点时需要的步数）。
判断重复点的过程循环次数过多，可以剪枝。在枚举时，跳过之前走过的点，直接选择没走过的，从而减少循环次数。
并查集跳过重复点的思路：访问到一个节点时，将该节点的根节点指针指向相邻的下一个节点，这样下次访问到这个节点时，可以跳到下一个未访问的节点。

二：动态规划+优先队列

代码

一：BFS + 并查集

type point struct {
	x, y     int
	priority int
}
func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}
type UnionFind struct {
	Fa []int
}
func NewUnionFind(n int) UnionFind {
	fa := make([]int, n)
	for i := range fa {
		fa[i] = i
	}
	return UnionFind{fa}
}
func (u *UnionFind) Find(x int) int {
	if u.Fa[x] != x {
		u.Fa[x] = u.Find(u.Fa[x])
	}
	return u.Fa[x]
}
func (u *UnionFind) Merge(x, y int) {
	rx := u.Find(x)
	ry := u.Find(y)
	if rx != ry {
		u.Fa[rx] = u.Fa[ry]
	}
}
func (u *UnionFind) Same(x, y int) bool {
	return u.Find(x) == u.Find(y)
}

func minimumVisitedCells(grid [][]int) int {
	m := len(grid)
	n := len(grid[0])
	queue := make([]point, 0, m*n)
	queue = append(queue, point{0, 0, 1})
	rowUnion := make([]UnionFind, m)
	colUnion := make([]UnionFind, n)
	for i := range rowUnion {
		rowUnion[i] = NewUnionFind(n + 1)
	}
	for i := range colUnion {
		colUnion[i] = NewUnionFind(m + 1)
	}
	for len(queue) > 0 {
		cur := queue[0]
		queue = queue[1:]
		if cur.x == m-1 && cur.y == n-1 {
			return cur.priority
		}
		round := grid[cur.x][cur.y]
		for nx := colUnion[cur.y].Find(cur.x + 1); nx <= min(m-1, cur.x+round); nx = colUnion[cur.y].Find(nx + 1) {
			colUnion[cur.y].Merge(nx, nx+1)
			queue = append(queue, point{nx, cur.y, cur.priority + 1})
		}
		for ny := rowUnion[cur.x].Find(cur.y + 1); ny <= min(n-1, cur.y+round); ny = rowUnion[cur.x].Find(ny + 1) {
			rowUnion[cur.x].Merge(ny, ny + 1)
			queue = append(queue, point{cur.x, ny, cur.priority + 1})
		}
	}
	return -1
}